package leetcode_day._2021._202110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/12 8:36
 * 两数相除
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * 算法：数学  位运算
 * 除法就是被除数减去除数
 * 超时
 * 使用二分查找
 */
public class _12_29 {
    public static void main(String[] args) {
        //-2147483648 -1
        System.out.println(new _12_29().divide(-2147483648, -1));
    }

    public int divide(int dividend, int divisor) {
        long a = dividend, b = divisor;
        boolean flag = false;
        if (a < 0) {
            a = -a;
            flag = !flag;
        }
        if (b < 0) {
            b = -b;
            flag = !flag;
        }
        // 0 ~ dividend
        long l = 0, r = a;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (mul(mid, b) <= a) l = mid;
            else r = mid - 1;
        }
        r = flag ? -r : r;
        if (r > Integer.MAX_VALUE || r < -Integer.MAX_VALUE - 1) return Integer.MAX_VALUE;
        return (int) r;
    }
    long mul(long a, long b) {
        long res = 0;
        while (b > 0) {
            if ((b & 1) == 1) res += a;
            a += a;
            b >>= 1;
        }
        return res;
    }


}
